//某公司组织架构以二叉搜索树形式记录，节点值为处于该职位的员工编号。请返回第 cnt 大的员工编号。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：root = [7, 3, 9, 1, 5], cnt = 2
//       7
//      / \
//     3   9
//    / \
//   1   5
//输出：7
// 
//
// 示例 2： 
//
// 
//
// 
//输入: root = [10, 5, 15, 2, 7, null, 20, 1, null, 6, 8], cnt = 4
//       10
//      / \
//     5   15
//    / \    \
//   2   7    20
//  /   / \ 
// 1   6   8
//输出: 8 
//
// 
//
// 提示： 
//
// 
// 1 ≤ cnt ≤ 二叉搜索树元素个数 
// 
//
// 
//
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树 👍 423 👎 0


package LeetCode.editor.cn;

/**
  @author ldltd
  @date 2025-05-16 23:29:47
  @description LCR 174.寻找二叉搜索树中的目标节点
 */
public class ErChaSouSuoShuDeDiKdaJieDianLcof{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 ErChaSouSuoShuDeDiKdaJieDianLcof fun=new ErChaSouSuoShuDeDiKdaJieDianLcof();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

 // Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class Solution {
         //逆向的后续遍历，右中左
    //计数
    int res, cnt;
    public int findTargetNode1(TreeNode root, int cnt) {
        this.cnt = cnt;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root) {
        if(root == null) return;
        dfs(root.right);
        if(cnt == 0) return;
        if(--cnt == 0) res = root.val;
        dfs(root.left);
    }


    public int findTargetNode(TreeNode root, int cnt) {
        dfs(root, cnt);
        return res;
    }

    private int dfs(TreeNode root, int cnt) {
        if (root == null) return 0;

        int rightCount = dfs(root.right, cnt); // 右子树的节点数
        if (rightCount + 1 == cnt) { // 当前节点是第 cnt 大的
            res = root.val;
        }

        int leftCount = dfs(root.left, cnt - rightCount - 1); // 左子树只需要找 cnt - rightCount - 1
        return rightCount + 1 + leftCount; // 返回当前子树的总节点数
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
